#ifndef __SWAPPAIRS_H__
#define __SWAPPAIRS_H__

#include "ListHeader.h"

/*
* leetcode 24 两两交换链表中的节点
*/

/*
* 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点
* 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
*/

//注意: 是交换物理结点, 而不是交换节点中的值
List* SwapPairs(List* head) {
	//添加虚拟头节点, 当有指针指向操作两个节点的前一个节点时, 才能完成后续操作
	//(前一个节点的指向需要修改)
	List* dummyHead = new List;
	dummyHead->next = head;

	List* cur = dummyHead;

	//节点数为偶数 cur->next == nullptr
	//		 奇数 cur->next->next == nullptr
	while (cur->next != nullptr && cur->next->next != nullptr) {
		List* curNext = cur->next;
		List* curNextNext = cur->next->next;

		/*
		* cur -> first -> second -> next
		* cur -> second -> first -> next
		* cur = next
		*/

		//指针操作
		//第一个节点的 next 指向 第二个节点的 next
		//第二个节点的next 指向 第一个节点
		//第零个节点的 next 指向 第二个节点
		curNext->next = curNextNext->next;
		curNextNext->next = curNext;
		cur->next = curNextNext;

		cur = cur->next->next;
	}

	List* result = dummyHead->next;
	delete dummyHead;
	return result;
}

#endif // !__SWAPPAIRS_H__

